package com.linyaonan.leetcode.medium._105;

import java.util.HashMap;

/**
 * @author: Lin
 * @date: 2024/2/20
 */
public class ConstructBinaryTree3 {

    HashMap<Integer, Integer> inIndexMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 记录所有中序遍历的数值以及索引的关系，通过一个数值能唯一确定中序遍历的位置
        for (int i = 0; i < inorder.length; i++) {
            inIndexMap.put(inorder[i], i);
        }
        return build(preorder, inorder, 0, preorder.length - 1, 0);
    }

    public TreeNode build(int[] preorder, int[] inorder, int startIndex, int endIndex, int preIndex) {
        // 边界
        if (startIndex > endIndex || preIndex >= preorder.length) {
            return null;
        }
        int t = preorder[preIndex];
        final Integer inIndex = inIndexMap.get(t);
        TreeNode tt = new TreeNode(t);
        // 左边数字个数
        int leftWid = inIndex - startIndex;
        tt.left = build(preorder, inorder, startIndex, inIndex - 1, preIndex + 1);
        tt.right = build(preorder, inorder, inIndex + 1, endIndex,  leftWid + preIndex + 1);
        return tt;
    }

}
